package com.sortingalgorithm;

import java.util.Arrays;

/*
*   小顶堆
* */
public class SmallHeapSort {
    public static void main(String[] args) {
        int[] arr = {1,3,6,7,2,54,5,4,54};
        smallHeapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    // 小顶堆
    public static void smallHeapSort(int [ ] arr){
        // 构建小顶堆
        buildSmallHeap(arr);
        int currentIdx = 0;
        int size = arr.length;
        while (size > 1){
            // 交换顶节点和最后一个结点
            swap(arr,0,size- 1);
            size--;
            // 剩下的调整大顶堆
            adjustSmallHeap(arr,0,size);

        }

    }

    // 构建小顶堆
    private static void buildSmallHeap(int [] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for(int i = 0;i < arr.length;i++){
            int currentIdx = i;
            int fatherIdx = ((i - 1) >> 1);
            while (fatherIdx >  - 1 && arr[fatherIdx] > arr[currentIdx]){
                swap(arr,currentIdx,fatherIdx);
                currentIdx = fatherIdx;
                fatherIdx = ((currentIdx - 1) >> 1);
            }
        }

    }

    private static void adjustSmallHeap(int[] arr,int currentIdx,int size){
        int left = currentIdx * 2 + 1;
        int right = currentIdx * 2 + 2;
        int smallIdx;
        while (left < size){
            if(arr[left] > arr[right] && right < size){
                smallIdx = right;
            }else{
                smallIdx = left;
            }
            if(arr[currentIdx] < arr[smallIdx]){
                smallIdx = currentIdx;
            }
            if(currentIdx == smallIdx){
                return;
            }
            swap(arr,smallIdx,currentIdx);
            currentIdx = smallIdx;
            left = currentIdx * 2 + 1;
            right = currentIdx * 2 + 2;

        }
    }

    // 交换
    private static void swap(int [] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
